package 第12周_AVL树和红黑树;

import 第13周_哈希表和SQRT分解.HashTable;
import 第8周_二分搜索树.二分搜索树.BST;

import java.util.ArrayList;
import java.util.Random;

public class Main {

    public static void main(String[] args) {
        int n = 200000;

        Random random = new Random();
        ArrayList<Integer> testData = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            testData.add(random.nextInt(Integer.MAX_VALUE));
        }

        //Test BST
        long startTime = System.nanoTime();

        BST<Integer> bst = new BST<>();
        for (Integer x : testData){
            bst.add(x);
        }

        long endTime = System.nanoTime();
        double time = (endTime - startTime) / 1000000000.0;
        System.out.println("BST: " + time + " s");
        //----------------------------------------------------------------------

        //Test AVL
        long startTime1 = System.nanoTime();

        AVLTree<Integer, Integer> avl = new AVLTree<>();
        for (Integer x : testData){
            avl.add(x, null);
        }

        long endTime1 = System.nanoTime();
        double time1 = (endTime1 - startTime1) / 1000000000.0;
        System.out.println("AVL: " + time1 + " s");

        //----------------------------------------------------------------------


        //Test AVL
        long startTime2 = System.nanoTime();

        RBTree<Integer, Integer> rbt = new RBTree<>();
        for (Integer x : testData){
            rbt.add(x, null);
        }

        long endTime2 = System.nanoTime();
        double time2 = (endTime2 - startTime2) / 1000000000.0;
        System.out.println("RBT: " + time2 + " s");


        //----------------------------------------------------------------------


        //Test AVL
        long startTime3 = System.nanoTime();

        HashTable<Integer, Integer> ht = new HashTable<>();
        for (Integer x : testData){
            ht.add(x, null);
        }

        long endTime3 = System.nanoTime();
        double time3 = (endTime3 - startTime3) / 1000000000.0;
        System.out.println("ht: " + time3 + " s");
    }
}
